package HighMethod08;

/**
 * 回溯 输出一个数组的所有组合
 * 分析过程是层次分析
 * 执行过程相当于深度优先遍历树
 */
public class HuiSu {
    //递归实现
    public static void fun(int[] ar, int[] br, int i, int n) {
        if (i >= n) {
            for (int j = 0; j < n; j++) {
                if (br[j] == 1) {
                    System.out.printf("%3d", ar[j]);
                }
            }
            System.out.println();
        } else {
            br[i] = 1;      //left
            fun(ar, br, i + 1, n);
            br[i] = 0;         //right
            fun(ar, br, i + 1, n);
        }
    }

    //非递归实现（栈可以实现,此处不用栈，这里思路有点难理解但是重要）
    public static void funHuiSu(int[] ar, int[] br) {   //以下的分支条件判断是回溯法的一种通用形式
        int len = ar.length;
        int i = 0;
        br[i] = -1;
        //br[]的取值范围-1，0，1，2
        while (i >= 0) {            //i下标相当于驱动，br[i]=2相当于控制周期
            br[i] += 1;             //br[i] =1的时候输出
            if (br[i] == 2) {
                i = i - 1;
            } else if (i == len-1) {
                Print_Ar(ar,br);        //到最后一位，打印
            } else {
                i = i+1;
                br[i] = -1;
            }
        }
    }

    public static void Print_Ar(int[] ar,int[] br){
        int len = br.length;
        for (int j = 0; j < len; j++) {
            if (br[j] == 1) {
                System.out.printf("%3d", ar[j]);
            }
//            System.out.printf("%3d", br[j]);
        }
        System.out.println();
    }


    public static void main(String[] args) {
        int[] ar = {1, 2, 3};             //((2^ar.length)-1)
//        int []br = {0,0,0};
        int[] br = new int[3];
        fun(ar, br, 0, ar.length);
//        funHuiSu(ar, br);
    }
}
